| 翻訳と辞書 |
| circuits over sets of natural numbers ： ウィキペディア英語版 |
circuits over sets of natural numbers
Circuits over natural numbers are a mathematical model used in studying computational complexity theory. They are a special case of circuits. The object is a labeled directed acyclic graph the nodes of which evaluate to sets of natural numbers, the leaves are finite sets, and the gates are set operations or arithmetic operations.
As an algorithmic problem, the problem is to find if a given natural number is an element of the output node or if two circuits compute the same set. Decidability is still an open question.
== Formal definition ==
A natural number circuit is a circuit, i.e. a labelled directed acyclic graph of in-degree at most 2. The nodes of in-degree 0, the leaves, are finite sets of natural numbers, the labels of the nodes of in-degree 1 are −, where and the labels of the nodes of in-degree 2 are +, ×, ∪ and ∩, where , and ∪ and ∩ with the usual set meaning.
The subset of circuits which do not use all of the possible labels are also studied.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「circuits over sets of natural numbers」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|